UVa/836 - Largest submatrix/836.cpp

   1 #include <iostream>
   2 #include <vector>
   3
   4 using namespace std;
   5
   6 int main(){
   7   int C;
   8   cin >> C;
   9   string line;
  10   getline(cin, line);
  11   getline(cin, line);
  12   for (int c=0; c<C; c++){
  13     if (c > 0) cout << endl;
  14     vector<string> m;
  15     while (getline(cin, line) && line != ""){
  16       m.push_back("0" + line);
  17     }
  18     int n = m.size();
  19     m.insert(m.begin(), string(n+1, '0'));
  20
  21     /*
  22       dp[i][j] = suma de la matriz que va desde la esquina (0,0) hasta la esquina (i,j)
  23      */
  24     int dp[n+1][n+1];
  25     for (int i=0; i<=n; ++i)
  26       for (int j=0; j<=n; ++j)
  27         dp[i][j] = m[i][j] - '0';
  28
  29     for (int i=1; i<=n; ++i)
  30       for (int j=1; j<=n; ++j)
  31         dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
  32
  33     int answer = 0;
  34     for (int i=1; i<=n; ++i)
  35       for (int j=1; j<=n; ++j)
  36         for (int a=i; a<=n; ++a)
  37           for (int b=j; b<=n; ++b){
  38             if ( ( dp[a][b] - dp[a][j-1] - dp[i-1][b] + dp[i-1][j-1] ) == (a - i + 1)*(b - j + 1) ){
  39               answer = max(answer, (a-i+1)*(b-j+1));
  40             }
  41           }
  42
  43     cout << answer << endl;
  44
  45
  46   }
  47   return 0;
  48 }